package com.zjsru.oneday202208;

/**
 * @Author: likew
 * @Date: 2022/9/8
 * 优美的排列 II
 *
 * 假设该列表是 answer =[a1, a2, a3, ... , an] ，那么列表 [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] 中应该有且仅有 k 个不同整数。
 *
 * 输入：n = 3, k = 1
 * 输出：[1, 2, 3]
 * 解释：[1, 2, 3] 包含 3 个范围在 1-3 的不同整数，并且 [1, 1] 中有且仅有 1 个不同整数：1
 *
 */
public class ConstructArray {
    /**
     * 需要构造首位开始按照「升序」间隔排列，次位开始按照「降序」间隔排列
     * （即排列为 [1, n, 2, n - 1, 3, ...]）时，相邻差值会从 n - 1n−1 开始递减至 11，共 n - 1 种。
     * */
    public int[] constructArray(int n, int k) {
        int[] ans = new int[n];
        int t = n - k - 1;
        for (int i = 0; i < t; i++) {
            ans[i] = i + 1;
        }
        for (int i = t, a = n - k, b = n; i < n; ) {
            ans[i++] = a++;
            if (i < n) {
                ans[i++] = b--;
            }
        }
        return ans;
    }
    
    public static void main(String[] args) {
        ConstructArray constructArray = new ConstructArray();
        int n = 6;
        int k = 2;
        System.out.println(constructArray.constructArray(n, k));
    }
}
